#include "linklist.h"
#include <iostream>
Linklist::Linklist() : size(0)
{
    head = new Node(0);
}

Linklist::Linklist(const Linklist &list)
{
    
    head = new Node(0);
    Node *TP = list.head->next;
    while (TP != nullptr)
    {
        InsertTail(TP->value);
        TP = TP->next;
    }
}

Linklist::~Linklist()
{
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 记录下一个节点
        delete head;                 // 放掉当前指针
        head = nextNode;             // head指针往后走
    }
}

void Linklist::InsertTail(const ElementType &element)
{
    Node *travelPoint = head; // 遍历指针 o(n)
    // 找尾部
    while (travelPoint->next != nullptr)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->next = new Node(element);

    size++;
}

void Linklist::InsertHead(const ElementType &element)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

void Linklist::InsertByIdenx(int index, const ElementType &element)
{
    if (index < 0 || index >= size)
    {
        return;
    }
    Node *travePoint = head;
    for (int i = 0; i < index; i++)
    {
        travePoint = travePoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travePoint->next;
    travePoint->next = newNode;
    size++;
}

void Linklist::RemoveByIdenx(int index)
{
    if (index < 0 || index >= size)
    {
        return;
    }

    Node *TP = head;
    for (int i = 0; i < index; i++) // index-1
    {
        TP = TP->next;
    }
    Node *freeNode = TP->next;
    TP->next = freeNode->next;
    delete freeNode;
    size--;
}

void Linklist::RemoveByElement(const ElementType &element)
{
    Node *TP = head;
    while (TP->next != nullptr)
    {
        if (TP->next->value == element)
        {
            Node *freeNode = TP->next;
            TP->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            TP = TP->next;
    }
}

void Linklist::UpdateByindex(int index, const ElementType &element)
{
    if (index < 0 || index >= size)
    {
        return;
    }
    Node *TP = head->next;
    for (int i = 0; i < index; i++)
    {
        TP = TP->next;
    }
    TP->value = element;
}

void Linklist::UpdateByElement(const ElementType &oldv, const ElementType &newv)
{
    Node *TP = head->next;
    while (TP != nullptr)
    {
        if (TP->value == oldv)
        {
            TP->value = newv;
        }
        TP = TP->next;
    }
}

void Linklist::BubbleSort()
{
    std::cout << size << std::endl;
    for (int i = 0; i < size - 1; i++)
    {
        Node *TP = head; // 从头开始扫描链表
        for (int j = 0; j < size - i - 1; j++)
        {
            if (TP->next->value > TP->next->next->value)
            {
                Node *prevNode = TP->next;
                Node *nextNode = prevNode->next;
                TP->next = nextNode;
                prevNode->next = nextNode->next;
                nextNode->next = prevNode;
            }
            TP = TP->next;
        }
    }
}

Linklist Linklist::Merge(const Linklist &list)
{
    Linklist result;
    Node *p1 = head->next;
    Node *p2 = list.head->next;
    while (p1 && p2)
    {
        if (p1->value > p2->value)
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
        else
        {

            result.InsertTail(p1->value);
            p1 = p1->next;
        }
    }
    while (p1)
    {
        result.InsertTail(p1->value);
        p1 = p1->next;
    }
    while (p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }

    return Linklist();
}

void Linklist::Sort()
{
    FastSort(head->next,nullptr);
}

void Linklist::Reserve()
{
    Node*prev=nullptr;
    Node*cur=head->next;
    Node*Next=cur->next;
    while (Next!=nullptr)
    {
        cur->next=prev;//逆序
        prev=cur;
        cur=Next;
        Next=cur->next;
    }
    cur->next=prev;//最后一个节点
    head->next=cur;
}

void Linklist::Reserve2()
{

head->next=Reserve2(head->next);

}

void Linklist::show()
{
    Node *travePoint = head->next; // 存有效数据的第一个节点
    while (travePoint != nullptr)
    {
        std::cout << travePoint->value << " "; // 打印数据域
        travePoint = travePoint->next;
    }
    std::cout << std::endl;
}

void Linklist::FastSort(Node *start, Node *end)
{

    if (start==end)
    {
        return;
    }
    Node*temp=start;//基准值指针
    Node*slow=start;
    //快慢指针
    Node*fast=start->next;
    while (fast!=end)
    {
        //快指针所指的数据比基准值小
        if (fast->value<temp->value)
        {
            slow=slow->next;
            std::swap(fast->value,slow->value);
        }
        fast=fast->next;

    }
    std::swap(slow->value,temp->value);
    FastSort(start,slow);
    FastSort(slow->next,end);
}

Linklist::Node* Linklist::Reserve2(Node *node)
{   //返回值是新链表的头
    if (node->next==nullptr)
    {
        return node;
    }
    else
    {
        Node*newHeader=Reserve2(node->next);
        node->next->next=node;//逆序
        node->next=nullptr;//新尾巴指向空
        return newHeader;
    }
    

}
